Cycle space Totally Explained

Everything about Cycle Space totally explained

==The binary cycle space== In graph theory, certain vector spaces over the two-element field Z₂ are associated with an undirected graph; this allows one to use the tools of linear algebra to study graphs.
   Let G be a finite simple undirected graph with edge set E. The power set of E becomes a Z₂-vector space if we take the symmetric difference as addition. Every element of this vector space can be thought of as a linear combination of edges with coefficient from Z₂. In yet another interpretation, the elements of this space are the functions E -> Z₂. This is the (binary) edge space of G. Its zero is the empty set, and the one-element sets form a basis, so its dimension is equal to the number of edges of G.
   An important subspace of the edge space is the (binary) cycle space. It is by definition the subspace generated by (the edge sets of) all the simple cycles of the graph. The addition of two cycles (shown dashed) is illustrated in the figure. Note that the result here (also shown dashed) isn't a simple cycle but an edge-disjoint union of two simple cycles. There are a number of basic results concerning the cycle space. The symmetric difference of two simple cycles is either a simple cycle or a union of edge-disjoint simple cycles. Using this observation, one can show that an edge set is in the cycle space if and only if it's a disjoint union of simple cycles. Phrased another way: the set F of edges is in the cycle space if and only if every vertex in the subgraph spanned by F has even degree.
   It isn't necessary to use all cycles to generate the cycle space: if G is connected and any spanning tree T of G is given, then the fundamental cycles of T form a basis of the cycle space. The dimension of the cycle space of a connected graph is thus related to the number of vertices and edges of the graph. If the graph has n vertices and m edges then the dimension is m-n+1.
   An important application of the cycle space are Whitney's planarity criterion and Mac Lane's planarity criterion, which give an algebraic characterization of the planar graphs.

The integral cycle space

The foregoing development can be carried out over the integers, Z. The integral edge space is the abelian group Z^E of functions from the edge set E to the integers. It is necessary (for the notation) to choose an arbitrary orientation of the graph in order to define the cycle space, but the definition doesn't depend on that choice. An integral cycle is a function such that the sum of values on edges oriented into a vertex x equals the sum of values on edges oriented out of x, for every vertex x. The set of integral cycles is a subgroup of the integral edge space. A cycle that never takes the value zero is called nowhere zero.
Reversing the orientation of an edge negates the value of a cycle on that edge. It is in this sense that the theory is independent of the arbitrary orientation. Given any one cycle, the orientation can be chosen so that cycle takes only nonnegative values.
An integral cycle whose maximum absolute value on any edge is less than k, a positive integer, is sometimes called a k-flow on G. W.T. Tutte developed an extensive theory of nowhere-zero k-flows that's in some ways dual to that of graph coloring.

The cycle space over a field or commutative ring

The construction of the integral cycle space can be carried out for any field, abelian group, or (most generally) commutative ring (with unity) R replacing the integers. If R is a field, the cycle space is a vector space over R with dimension m - n + c, where c is the number of connected components of G. If R is any commutative ring, the cycle space is a free R-module with rank m - n + c.
When R is an abelian group such a cycle may also be called an R-flow on G. Nowhere-zero R-flows for a finite abelian group R of k elements are related to nowhere-zero integral k-flows in Tutte's theory. The number of nowhere-zero R-cycles is an evaluation of the Tutte polynomial, dual to the number of proper colorings of the graph (Tutte, 1984, Section IX.4).

Further Information

Get more info on 'Cycle Space'.

External Link Exchanges

Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:

<a href="http://cycle_space.totallyexplained.com">Cycle space Totally Explained</a>

Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned.